翻訳と辞書 Words near each other ・ Quadropus ・ Quadrula ・ Quadrula metanevra ・ Quadrula pustulosa ・ Quadrula quadrula ・ Quadrula refulgens ・ Quadrula rumphiana ・ Quadrula tuberosa ・ Quadrumana ・ Quadratic integrate and fire ・ Quadratic irrational ・ Quadratic Jordan algebra ・ Quadratic Lie algebra ・ Quadratic mean diameter ・ Quadratic pair ・ Quadratic probing ・ Quadratic programming ・ Quadratic reciprocity ・ Quadratic residue ・ Quadratic residue code ・ Quadratic residuosity problem ・ Quadratic set ・ Quadratic sieve ・ Quadratic transformation ・ Quadratic unconstrained binary optimization ・ Quadratic variation ・ Quadratic-linear algebra ・ Quadratically closed field ・ Quadratically constrained quadratic program ・ Quadratics Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Quadratic probing ： ウィキペディア英語版 Quadratic probing Quadratic probing is an open addressing scheme in computer programming for resolving collisions in hash tables—when an incoming data's hash value indicates it should be stored in an already-occupied slot or bucket. Quadratic probing operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until an open slot is found. For a given hash value, the indices generated by linear probing are as follows: $H\; +\; 1\; ,\; H\; +\; 2\; ,\; H\; +\; 3\; ,\; H\; +\; 4\; ,\; ...\; ,\; H\; +\; k$ This method results in primary clustering, and as the cluster grows larger, the search for those items hashing within the cluster becomes less efficient. An example sequence using quadratic probing is: $H\; +\; 1^2\; ,\; H\; +\; 2^2\; ,\; H\; +\; 3^2\; ,\; H\; +\; 4^2\; ,\; ...\; ,\; H\; +\; k^2$ Quadratic probing can be a more efficient algorithm in a closed hash table, since it better avoids the clustering problem that can occur with linear probing, although it is not immune. It also provides good memory caching because it preserves some locality of reference; however, linear probing has greater locality and, thus, better cache performance. Quadratic probing is used in the Berkeley Fast File System to allocate free blocks. The allocation routine chooses a new cylinder-group when the current is nearly full using quadratic probing, because of the speed it shows in finding unused cylinder-groups. ==Quadratic function== Let h(k) be a hash function that maps an element k to an integer in (), where m is the size of the table. Let the ith probe position for a value k be given by the function :$h(k,i)\; =\; (\; h(k)\; +\; c\_1\; i\; +\; c\_2\; i^2\; )\; \backslash pmod$ where c2 ≠ 0. If c2 = 0, then h(k,i) degrades to a linear probe. For a given hash table, the values of c1 and c2 remain constant. Examples: *If $h(k,i)\; =\; (h(k)\; +\; i\; +\; i^2)\; \backslash pmod$, then the probe sequence will be $h(k),\; h(k)+2,\; h(k)+6,\; ...$ *For m = 2n, a good choice for the constants are c1 = c2 = 1/2, as the values of h(k,i) for i in () are all distinct. This leads to a probe sequence of $h(k),\; h(k)+1,\; h(k)+3,\; h(k)+6,\; ...$ where the values increase by 1, 2, 3, ... *For prime m > 2, most choices of c1 and c2 will make h(k,i) distinct for i in ((m-1)/2 ). Such choices include c1 = c2 = 1/2, c1 = c2 = 1, and c1 = 0, c2 = 1. Because there are only about m/2 distinct probes for a given element, it is difficult to guarantee that insertions will succeed when the load factor is > 1/2. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Quadratic probing」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.